import java.util.Arrays;

/**
 * 快速排序
 * 
 * 快速排序的基本思想
 * 1). 先从数列中取出一个数作为基准数。
2). 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3). 再对左右区间重复第二步，直到各区间只有一个数。
 * 
 */
public class 快排Demo {
    
    public static void main(String[] args) {

        int[] nums = new int[]{22,3,18,74,32,52,162,14,18,362,132,44};

        doQuickSort(nums, 0, nums.length-1);

        Arrays.stream(nums).boxed().map(s -> s+",").forEach(System.out::print);
        System.out.println();


    }

    private static void doQuickSort(int[] nums, int startPosition, int endPosition){

        if(nums.length < 0){
            return;
        }

        if(startPosition >= endPosition){

            return;
        }

        int left = startPosition;
        int right = endPosition;

        int temp = nums[left];

        while (left < right) {
            
            while (left < right && nums[right] >= temp){
                right -- ;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= temp){
                left ++ ;
            }
            nums[right] = nums[left];
        }

        nums[left] = temp;

        //int 数组 转 string 数组
        // Arrays.stream(nums).boxed().map(s -> s+",").forEach(System.out::print);

        // System.out.println();

        doQuickSort(nums, startPosition, left -1);
        doQuickSort(nums,left+1, endPosition);

    }
}
